package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class TreeNodeRightSideView {

	private List<Integer> list = new ArrayList<Integer>();
	
	public static void main(String[] args) {
		int[] pre = { 1, 3, 4, 2, 6, 7, 8, 5, 9 };
		int[] in = { 4, 6, 2, 8, 7, 3, 1, 9, 5 };
		TreeNodeRightSideView object = new TreeNodeRightSideView();
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		System.out.println(object.rightSideView(root));
	}
	
	public List<Integer> rightSideView(TreeNode root) {
		list.clear();
		if (root == null) {
			return list;
		}
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		int nextLevel = 0; // 下一层中的节点
		int curLevel = 1;
		int toBePrint = 1; // 该层中等待被打印的结点
		while (!queue.isEmpty()) {
			TreeNode node = queue.getFirst();
			if(toBePrint == curLevel){
				list.add(node.val);
			}
			if (node.right != null) {
				queue.add(node.right);
				nextLevel++;
			}
			if (node.left != null) {
				queue.add(node.left);
				nextLevel++;
			}
			queue.remove();
			toBePrint--;
			// 这一层中的全部打印完
			if (toBePrint == 0) {
				// toBePrint设置为nextLevel，此时再下一层nextLevel为0
				toBePrint = nextLevel;
				curLevel = nextLevel;
				nextLevel = 0;
			}
		}
		return list;
	}
	
	//other's idea
	public List<Integer> rightSideView2(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        //通过currDepth是否与result的长度相等老判断是否已经将该层最右边的数据加入了
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        //这里要先遍历右子树
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);
    }
}
